# 169. 多数元素
# 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
import collections
import random


def majorityElement(nums: list):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums)
    num_dict = {}
    for num in nums:
        count = num_dict.get(num, 0)
        num_dict[num] = count + 1
    for item in num_dict.items():
        if item[1] > n / 2:
            return item[0]
    return None


def majorityElement_hash(nums: list):
    # Counter 是 dict 的一个子类，用来统计 hashtable 的每个元素的数量
    counter = collections.Counter(nums)
    print(f"counter {counter}")
    return max(counter.keys(), key=counter.get)


def majorityElement_sort_half(nums: list):
    nums.sort()
    print(f"nums {nums}")
    return nums[len(nums) // 2]


def majorityElement_random(nums: list):
    # 中间数的下标
    majority_count = len(nums) // 2
    while True:
        # 随机选一个数
        candidate = random.choice(nums)
        print(f"random.choice majority_count : {majority_count} , candidate : {candidate}")
        # 统计所有选择的数，如果大于总数的一半，说明是众数
        if sum(1 for num in nums if num == candidate) > majority_count:
            return candidate


# Boyer-Moore 投票算法
# 思路
# 如果我们把众数记为 +1+1+1，把其他数记为 −1-1−1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
def majorityElement_boyer_moore(nums: list):
    # 中间数的下标
    candidate = None
    count = 0
    for index in range(len(nums)):
        if count == 0:
            candidate = nums[index]

        if candidate == nums[index]:
            count += 1
        else:
            count -= 1

    return candidate


nums_1 = [3, 3, 3, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1]
result = majorityElement_boyer_moore(nums_1)
print(result)
